<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>算法可视化解析：strStr()实现</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            color: #333;
            line-height: 1.6;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #6e8efb 0%, #a777e3 100%);
        }
        .code-block {
            background: #2d2d2d;
            border-left: 4px solid #a777e3;
        }
        .algorithm-card:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 25px -5px rgba(0, 0, 0, 0.1), 0 10px 10px -5px rgba(0, 0, 0, 0.04);
        }
        .highlight {
            position: relative;
        }
        .highlight::after {
            content: '';
            position: absolute;
            bottom: 0;
            left: 0;
            width: 100%;
            height: 30%;
            background-color: rgba(167, 119, 227, 0.2);
            z-index: -1;
            transition: all 0.3s ease;
        }
        .highlight:hover::after {
            height: 100%;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="container mx-auto max-w-4xl">
            <div class="flex flex-col items-center text-center">
                <h1 class="text-4xl md:text-5xl font-bold mb-6 font-serif">strStr() <span class="text-yellow-200">算法解析</span></h1>
                <p class="text-xl md:text-2xl mb-8 max-w-2xl leading-relaxed">
                    深入理解字符串匹配的核心算法，掌握KMP与暴力匹配的精髓
                </p>
                <div class="flex space-x-4">
                    <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">#字符串匹配</span>
                    <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">#算法优化</span>
                    <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">#LeetCode</span>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <div class="container mx-auto max-w-4xl px-6 py-16">
        <!-- Problem Statement -->
        <section class="mb-20">
            <h2 class="text-3xl font-bold mb-6 text-gray-800 font-serif flex items-center">
                <i class="fas fa-question-circle text-purple-600 mr-3"></i>
                问题描述
            </h2>
            <div class="bg-white rounded-xl shadow-md p-8 border-l-4 border-purple-500">
                <p class="text-lg mb-4">实现 <span class="highlight font-mono font-bold">strStr()</span> 函数，该函数返回子串在原串中第一次出现的位置，如果不存在则返回 <span class="highlight font-mono font-bold">-1</span>。</p>
                <div class="flex items-start mt-6">
                    <div class="flex-shrink-0 bg-purple-100 rounded-full p-3 mr-4">
                        <i class="fas fa-lightbulb text-purple-600 text-xl"></i>
                    </div>
                    <div>
                        <h4 class="font-bold text-gray-800 mb-2">关键点</h4>
                        <ul class="list-disc pl-5 space-y-1 text-gray-700">
                            <li>空字符串的处理</li>
                            <li>边界条件的考虑</li>
                            <li>效率优化</li>
                        </ul>
                    </div>
                </div>
            </div>
        </section>

        <!-- Algorithm Visualization -->
        <section class="mb-20">
            <h2 class="text-3xl font-bold mb-6 text-gray-800 font-serif flex items-center">
                <i class="fas fa-project-diagram text-purple-600 mr-3"></i>
                算法可视化
            </h2>
            <div class="grid md:grid-cols-2 gap-8">
                <div class="bg-white rounded-xl shadow-md overflow-hidden">
                    <div class="p-6">
                        <h3 class="text-xl font-bold mb-4 text-purple-600">暴力匹配法</h3>
                        <p class="text-gray-700 mb-4">最直观的解决方案，逐个位置尝试匹配子串。</p>
                        <div class="mermaid">
                            graph TD
                                A[开始] --> B[初始化i=0]
                                B --> C{i <= len(haystack)-len(needle)?}
                                C -->|是| D[比较haystack[i..i+n]和needle]
                                D --> E{匹配?}
                                E -->|是| F[返回i]
                                E -->|否| G[i++]
                                G --> C
                                C -->|否| H[返回-1]
                                F --> I[结束]
                                H --> I
                        </div>
                    </div>
                </div>
                <div class="bg-white rounded-xl shadow-md overflow-hidden">
                    <div class="p-6">
                        <h3 class="text-xl font-bold mb-4 text-purple-600">KMP算法</h3>
                        <p class="text-gray-700 mb-4">更高效的方法，利用部分匹配表跳过不必要比较。</p>
                        <div class="mermaid">
                            graph TD
                                A[开始] --> B[构建部分匹配表]
                                B --> C[初始化i=0,j=0]
                                C --> D{i < len(haystack)?}
                                D -->|是| E{haystack[i]==needle[j]?}
                                E -->|是| F[j++, i++]
                                F --> G{j==len(needle)?}
                                G -->|是| H[返回i-j]
                                G -->|否| D
                                E -->|否| I{j>0?}
                                I -->|是| J[j=pmt[j-1]]
                                I -->|否| K[i++]
                                J --> E
                                K --> D
                                D -->|否| L[返回-1]
                                H --> M[结束]
                                L --> M
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Solution Code -->
        <section class="mb-20">
            <h2 class="text-3xl font-bold mb-6 text-gray-800 font-serif flex items-center">
                <i class="fas fa-code text-purple-600 mr-3"></i>
                示例代码
            </h2>
            <div class="bg-white rounded-xl shadow-md overflow-hidden algorithm-card transition-all duration-300">
                <div class="px-6 py-4 border-b border-gray-200 flex justify-between items-center">
                    <h3 class="font-bold text-lg">暴力匹配实现</h3>
                    <div class="flex space-x-2">
                        <span class="px-2 py-1 bg-purple-100 text-purple-800 text-xs rounded-full">Python</span>
                        <span class="px-2 py-1 bg-blue-100 text-blue-800 text-xs rounded-full">O(m*n)</span>
                    </div>
                </div>
                <div class="code-block p-6">
                    <pre class="text-gray-100 font-mono text-sm overflow-x-auto">
<span class="text-purple-400">def</span> <span class="text-yellow-300">strStr</span>(haystack, needle):
    <span class="text-gray-500"># 处理空字符串情况</span>
    <span class="text-purple-400">if</span> <span class="text-purple-400">not</span> needle:
        <span class="text-purple-400">return</span> <span class="text-green-400">0</span>
    
    <span class="text-purple-400">for</span> i <span class="text-purple-400">in</span> <span class="text-blue-400">range</span>(<span class="text-blue-400">len</span>(haystack) - <span class="text-blue-400">len</span>(needle) + <span class="text-green-400">1</span>):
        <span class="text-purple-400">if</span> haystack[i:i+<span class="text-blue-400">len</span>(needle)] == needle:
            <span class="text-purple-400">return</span> i
    <span class="text-purple-400">return</span> -<span class="text-green-400">1</span></pre>
                </div>
            </div>
        </section>

        <!-- Complexity Analysis -->
        <section>
            <h2 class="text-3xl font-bold mb-6 text-gray-800 font-serif flex items-center">
                <i class="fas fa-chart-bar text-purple-600 mr-3"></i>
                复杂度分析
            </h2>
            <div class="grid md:grid-cols-3 gap-6">
                <div class="bg-white rounded-xl shadow-md p-6 border-t-4 border-purple-500">
                    <div class="flex items-center mb-4">
                        <div class="bg-purple-100 text-purple-600 p-3 rounded-full mr-4">
                            <i class="fas fa-clock text-xl"></i>
                        </div>
                        <h3 class="font-bold text-lg">时间复杂度</h3>
                    </div>
                    <p class="text-gray-700">暴力匹配：O(m×n)</p>
                    <p class="text-gray-700">KMP算法：O(m+n)</p>
                    <p class="text-sm text-gray-500 mt-2">m为主串长度，n为子串长度</p>
                </div>
                <div class="bg-white rounded-xl shadow-md p-6 border-t-4 border-blue-500">
                    <div class="flex items-center mb-4">
                        <div class="bg-blue-100 text-blue-600 p-3 rounded-full mr-4">
                            <i class="fas fa-memory text-xl"></i>
                        </div>
                        <h3 class="font-bold text-lg">空间复杂度</h3>
                    </div>
                    <p class="text-gray-700">暴力匹配：O(1)</p>
                    <p class="text-gray-700">KMP算法：O(n)</p>
                    <p class="text-sm text-gray-500 mt-2">KMP需要存储部分匹配表</p>
                </div>
                <div class="bg-white rounded-xl shadow-md p-6 border-t-4 border-green-500">
                    <div class="flex items-center mb-4">
                        <div class="bg-green-100 text-green-600 p-3 rounded-full mr-4">
                            <i class="fas fa-balance-scale text-xl"></i>
                        </div>
                        <h3 class="font-bold text-lg">选择建议</h3>
                    </div>
                    <p class="text-gray-700">短字符串：暴力匹配</p>
                    <p class="text-gray-700">长字符串/多次查询：KMP</p>
                    <p class="text-sm text-gray-500 mt-2">根据实际场景权衡</p>
                </div>
            </div>
        </section>
    </div>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'dark',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>